class Solution
{
public:
    long long sellingWood(int m, int n, vector<vector<int>> &prices)
    {
        unordered_map<int, int> priceMap;
        for (auto &p : prices)
        {
            int w = p[0];
            int h = p[1];
            int price = p[2];
            priceMap[w * 20001 + h] = price;
        }

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, -1));
        dp[0][0] = 0;
        function<long long(int, int)> dfs = [&](int w, int h) -> long long
        {
            if (dp[w][h] != -1)
            {
                return dp[w][h];
            }
            long long result = 0;
            if (priceMap.count(w * 20001 + h))
            {
                result = priceMap[w * 20001 + h];
            }
            for (int i = 1; i < w; i++)
            {
                result = max(result, dfs(i, h) + dfs(w - i, h));
            }
            for (int i = 1; i < h; i++)
            {
                result = max(result, dfs(w, i) + dfs(w, h - i));
            }
            dp[w][h] = result;
            return result;
        };
        return dfs(m, n);
    }
};